Rigging the Bovine Election   cowrig.X

It's election time. The farm is partitioned into a 5x5 grid of cow
locations, each of which holds either a Holstein ('H') or Jersey
('J') cow.  The Jerseys want to create a voting district of 7 contiguous
(vertically or horizontally) cow locations such that the Jerseys outnumber
the Holsteins. How many ways can this be done for the supplied grid?

PROBLEM NAME: cowrig.X

INPUT FORMAT:

* Lines 1..5: Each of the five lines contains five characters per
        line, each 'H' or 'J'.  No spaces are present.

SAMPLE INPUT:

HHHHH
JHJHJ
HHHHH
HJHHJ
HHHHH

OUTPUT FORMAT:

* Line 1: The number of distinct districts of 7 connected cows such
        that the Jerseys outnumber the Holsteins in the district.

SAMPLE OUTPUT:

2

OUTPUT DETAILS:

The two possible districts are:
.....                .....
JHJHJ                JHJHJ
....H       and      .H...
....J                .J...
.....                .....

Any other possible district with seven cows has fewer than 4 Jerseys.

============================= WRITEUP =================================

The key insight to this problem is that it is in fact brute-forceable. There are only 25 choose 7 = 480700 possibilities to search through. Even the process of checking all of these for contiguousness only increases the number of operations to a few million, and although this may be too slow for the ACM, it should work quite well given any competition without significant time constraints.

There are essentially three steps:

1. Generate all possible selections of 7 pastures.

2. Remove all noncontiguous selections.

3. Count the number of selections where there are 4 or more Jersey cows, and print the count when done.

A less-brute force way of doing might be to breadth-first search with depth 7 from every point in the matrix, and store each path so generated in a set, rather than a list, since a set won't store copies. However I have not tried this approach.

============================== CODE ===================================
#in python

#essentially a slightly modified indexof function.
def getThing(i, j, seq):
    for e in seq:
        if(e[0] == i and e[1] == j):
            return e
    return 0

#given a sequence of seven triples containing their x and y 
#positions and whether they have a Jersey or a Holstein cow,
#determine whether the sequence is connected (cow type is 
#actually irrelevant here so it could work with pairs).

#The way the function works is by using, essentially, 
#a grid-wise breadth-first search. Essentially, if the program 
#runs out of connected squares to which it can traverse from the
#starting position, and there are still elements in sequence that
#have not been visited (and therefore removed from the list), then
#the collection is discontiguous, because I cannot reach all locations
#in the collection from the starting point.

def isContig(seq):
    myq = []
    myq.append(seq.pop(0))
    while len(myq) > 0 and len(seq) > 0:
        elt = myq.pop(0)
        n = getThing(elt[0]-1, elt[1], seq)
        if n != 0:
            seq.remove(n)
            myq.append(n)
        n = getThing(elt[0]+1, elt[1], seq)
        if n != 0:
            seq.remove(n)
            myq.append(n)
        n = getThing(elt[0], elt[1]-1, seq)
        if n != 0:
            seq.remove(n)
            myq.append(n)
        n = getThing(elt[0], elt[1]+1, seq)
        if n != 0:
            seq.remove(n)
            myq.append(n)
    return len(seq) == 0

#This function generates all of possible districts recursively, and 
#once they have length 7 checks them to make sure they are contiguous
#and have a Jersey majority. 
def genStuff(list, howmanyleft, chosenpastures):
    if len(list) < howmanyleft: # if the number of spaces you have
					  # left to fill is greater than the
					  # the number of choices you have left
					  # you can't fill them, so the district
					  # is invalid.

    elif howmanyleft == 0:	# if you have generated a list of 7 				      # pastures

        js = 0
        for e in chosenstuff: # count the number of Jersey cows in
            if e[2] == 'J':	# the district
                js += 1
        if js < 4:		# Return 0 if they aren't a majority
            return 0
        else:
            if isContig(list(chosenstuff)):  #if Jerseys are a majority
                return 1			   #and districti contiguous

            else:					#if district is discontiguous
                return 0
    else: 
	  #This is where the recursive calls take place. 
        #n1 does not enqueue the current location, while n2 does.
	  #This works because for any pature i, it considers all 
	  #districts excluding i, and all including i.
        n1 = genStuff(list[1:], howmanyleft, chosenpastures)
        n2 = genStuff(list[1:], howmanyleft-1, \
                                chosenpastures + [list[0]])
        return n1 + n2

def main():
    listyThing = []

    # for convenience sake, we store things in a one dimensional
    # array with each element having x and y index and cow-type 

    for i in range(5):
        row = raw_input()
        for j in range(5):
            listyThing.append([i, j, row[j]]) 

    print genStuff(listyThing, 7, [])

if __name__ == "__main__":
    main()